package java学习.算法.二叉树;

import java.util.*;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/4/26 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
 class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
public class print之 {
    public class Solution {
//        队列
        public ArrayList<ArrayList<Integer>> Print1(TreeNode pRoot) {
            ArrayList<ArrayList<Integer>> list = new ArrayList<>();
            int d = 1;
            if(pRoot ==null){
                return list;
            }
//       队列
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(pRoot);
            while (!queue.isEmpty()){
                d++;
                ArrayList<Integer> listNum = new ArrayList<>();
                int n  = queue.size();
            for (int i = 0; i < n ; i++) {
                TreeNode poll = queue.poll();
                if(d%2==0){
                    listNum.add(poll.val);
                }else {
                    listNum.add(0,poll.val);
                }


                if (poll.left!=null){
                    queue.offer(poll.left);
                }

                if (poll.right!=null){
                    queue.offer(poll.right);
                }

                }
                list.add(listNum);
            }
        return  list;
        }

//        双栈
        /*
        1. 奇数  栈放s1， 偶数  栈放s2
        2. 奇数层 从左到右输出，即 右到左压栈 ，压入s2
           偶数层  左到右压栈               ，压入s1
        3.  在 s1 出栈时，s2 压栈
            在 s2 出栈时， s1 压栈
         */
        public ArrayList<ArrayList<Integer>> Print2(TreeNode pRoot) {
            ArrayList<ArrayList<Integer>> list = new ArrayList<>();
            int d = 1;
            if (pRoot == null) {
                return list;
            }
            Stack<TreeNode> s1 = new Stack<>(); //奇数
            Stack<TreeNode> s2 = new Stack<>(); //偶数
            s1.push(pRoot);
            while (!s1.empty() || !s2.empty()) {
                //奇数
                if (d % 2 != 0) {
                    ArrayList<Integer> arrayList1 = new ArrayList<>();
                    while (!s1.empty()) {
                        TreeNode pop = s1.pop();
                        arrayList1.add(pop.val);
                        if (pop.left != null) {
                            s2.push(pop.left);
                        }
                        if (pop.right != null) {
                            s2.push(pop.right);
                        }
                    }
                    if (arrayList1 != null) {

                        list.add(arrayList1);
                        d++;

                    }

                } else {
                    ArrayList<Integer> arrayList2 = new ArrayList<>();
                    while (!s2.isEmpty()) {
                        TreeNode pop = s2.pop();
                        if (pop != null) {  // 出栈的不能为空
//                        while 循环，每次都会将出栈的加入 arraylist2
                            arrayList2.add(pop.val);
                            if (pop.right != null) {
                                s1.push(pop.right);
                            }
                            if (pop.left != null) {
                                s1.push(pop.left);
                            }
                        }

                    }

                    // 将arraylist2 加入list
                    if (arrayList2 != null) {
                        list.add(arrayList2);

                        d++;
                    }
                }



            }
            return list;
        }

        }
}
